package org.example.leetCode;

import java.util.Arrays;

/**
 * 56. 合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 */
public class Code56 {
    public int[][] merge(int[][] intervals) {
        // 边界条件检查
        if (intervals.length <= 1) {
            return intervals;
        }

        // 按照区间起始位置排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // 使用动态数组思想，双指针处理
        int[][] result = new int[intervals.length][];
        int count = 0;

        for (int i = 0; i < intervals.length; i++) {
            // 如果结果数组为空，或者当前区间与上一个结果区间不重叠
            if (count == 0 || result[count - 1][1] < intervals[i][0]) {
                result[count++] = intervals[i];
            } else {
                // 合并区间：更新上一个结果区间的结束位置
                result[count - 1][1] = Math.max(result[count - 1][1], intervals[i][1]);
            }
        }

        // 返回实际使用的部分
        return Arrays.copyOf(result, count);
    }

    public static void main(String[] args) {
        Code56 solution = new Code56();

        // 测试用例1: [[1,3],[2,6],[8,10],[15,18]]
        int[][] intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] result1 = solution.merge(intervals1);
        System.out.println("输入: [[1,3],[2,6],[8,10],[15,18]]");
        System.out.println("输出: " + Arrays.deepToString(result1));
        // 预期输出: [[1,6],[8,10],[15,18]]

        // 测试用例2: [[1,4],[4,5]]
        int[][] intervals2 = {{1, 4}, {4, 5}};
        int[][] result2 = solution.merge(intervals2);
        System.out.println("输入: [[1,4],[4,5]]");
        System.out.println("输出: " + Arrays.deepToString(result2));
        // 预期输出: [[1,5]]

        // 测试用例3: [[1,4],[0,4]]
        int[][] intervals3 = {{1, 4}, {0, 4}};
        int[][] result3 = solution.merge(intervals3);
        System.out.println("输入: [[1,4],[0,4]]");
        System.out.println("输出: " + Arrays.deepToString(result3));
        // 预期输出: [[0,4]]

        // 测试用例4: [[1,4],[2,3]]
        int[][] intervals4 = {{1, 4}, {2, 3}};
        int[][] result4 = solution.merge(intervals4);
        System.out.println("输入: [[1,4],[2,3]]");
        System.out.println("输出: " + Arrays.deepToString(result4));
        // 预期输出: [[1,4]]
    }
}
